package everydayGrade.t3;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author: Siantar
 * @Date: 2024-03-05-22:39
 * @Description: 1.0
 */
public class T1976 {
    public int countPaths(int n, int[][] roads) {
        List<int[]>[] mp = creatTable(roads, n);
        long[] f = dijkstra(mp, 0);
        return (int) f[n - 1];
    }

    public List<int[]>[] creatTable(int[][] edges, int n) {
        List<int[]>[] mp = new List[n];
        for (int i = 0; i < n; ++i) {
            mp[i] = new ArrayList<int[]>();
        }
        for (int[] e : edges) {
            int from = e[0], to = e[1], weight = e[2];
            mp[from].add(new int[]{to, weight});
            mp[to].add(new int[]{from, weight});
        }
        return mp;
    }

    public long[] dijkstra(List<int[]>[] mp, int s) {
        int n = mp.length;
        int[] dis = new int[n];
        long[] f = new long[n];
        boolean[] vis = new boolean[n];
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a, b) -> a - b);
        Arrays.fill(dis, Integer.MAX_VALUE / 2);
        dis[s] = 0;
        f[s] = 1;
        queue.offer(s);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            if (vis[u]) continue;
            vis[u] = true;
            for (int[] vw : mp[u]) {
                int v = vw[0], w = vw[1];
                //核心代码
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    f[v] = f[u];
                    queue.offer(v);
                } else if (dis[v] == dis[u] + w) {
                    f[v] = (f[v] + f[u]) % 1_000_000_007;
                }
            }
        }
        return f;
    }
}
